/*
 * ModelCC, distributed under ModelCC Shared Software License, www.modelcc.org
 */

package org.modelcc.parser.fence;

import java.io.Serializable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.modelcc.language.syntax.Grammar;
import org.modelcc.language.syntax.Rule;
import org.modelcc.language.syntax.RuleSymbol;
import org.modelcc.language.syntax.InputSymbol;
import org.modelcc.lexer.LexicalGraph;
import org.modelcc.lexer.Token;

/**
 * Fence Grammar Parser
 * 
 * @author Luis Quesada (lquesada@modelcc.org), partially refactored by Fernando Berzal (berzal@modelcc.org)
 */
public final class FenceGrammarParser implements Serializable 
{
    /**
     * The grammar.
     */
    private Grammar g;

    /**
	 * Lexical graph
	 */
	private LexicalGraph lg;
	
	/**
	 * Parse graph
	 */
	private ParsedGraph pg;

	
	// Handles & cores
	
    /**
     * Already generated handles.
     */
    private Map<ParsedSymbol,Set<WaitingHandle>> doneHandles;
    
    /**
     * Waiting handle pool.
     */
    private Stack<WaitingHandle> waitingHandlePool;
    
    /**
     * Cores.
     */
    private Map<ParsedSymbol,Map<Object,Set<Handle>>> cores;
        

    /**
     * Parse lexical graph
     * @param g the grammar
     * @param lg the lexical graph
     * @return a parsed graph
     */
    public ParsedGraph parse (Grammar g, LexicalGraph lg) 
    {
        this.g = g;
        this.lg = lg;
        this.pg = new ParsedGraph(g,lg);
        
        // Conversion to parse graph
        // -------------------------

        // Token -> ParsedSymbol correspondence map.
        Map<Token,ParsedSymbol> ttos = new HashMap<Token,ParsedSymbol>();

        // Generate correspondence map.
        for (Token t: lg.getTokens()) {
        	ParsedSymbol s = new ParsedSymbol(t.getType(),t.getStartIndex(),t.getEndIndex(),t.getString());
        	s.setUserData(t.getUserData());
        	ttos.put(t,s);
        	pg.addSymbol(s);
        }

        // Complete preceding/following sets.
        for (Token t: lg.getTokens()) {
        	ParsedSymbol s = ttos.get(t);
        	List<Token> prec = lg.getPreceding(t);
        	if (prec != null)
        		for (Token k: prec)
        			pg.addLink(ttos.get(k),s);
        }

        for (ParsedSymbol s: pg.getSymbols()) {
        	if (s.getType().equals(g.getStartType()))
        		if (s.getStartIndex()==lg.getInputStartIndex() && s.getEndIndex()==lg.getInputEndIndex())
        			pg.addStart(s);
        	// vs. LZ version: if (preceding.get(s) == null && following.get(s) == null)
        }

        // Parsing
        // -------

        WaitingHandle wh;
        Object nextType;
        int skip;

        // Cores.
        cores = new HashMap<ParsedSymbol,Map<Object,Set<Handle>>>(256);
        for (ParsedSymbol s: pg.getSymbols()) {
        	cores.put(s,new HashMap<Object,Set<Handle>>());
        }

        // Waiting handle pool
        waitingHandlePool = new Stack<WaitingHandle>();

        // Done handles
        doneHandles = new HashMap<ParsedSymbol,Set<WaitingHandle>>(256);

        // Adds a handle with each rule to each core.
        for (ParsedSymbol s: pg.getSymbols()) {
        	Set<Rule> startRules = g.getStartRules(s.getType());
        	if (startRules != null) {
        		for (Rule r: startRules) {
        			addHandle(s,r,0,s);
        		}
        	}
        }

        // If start symbol accepts the empty string, add it.
        if (g.isNullable(g.getStartType()) && lg.getStart().isEmpty()) {
        	ParsedSymbol s = new ParsedSymbol(g.getStartType(),-1,-1);
        	pg.addSymbol(s);
        	pg.addStart(s);
        }

        // Process waiting handle pool.
        while (!waitingHandlePool.isEmpty()) {
        	wh = waitingHandlePool.pop();

        	if (wh.getMatched()==wh.getRule().getRight().size()-1) {
        		generateSymbol(g.getStartType(),wh);
        	} else {
        		Set<ParsedSymbol> foll = pg.getFollowing(wh.getNext());
        		if (foll != null) {
        			for (ParsedSymbol s: foll) {
        				addHandle(s,wh.getRule(),wh.getMatched()+1,wh.getFirst());
        			}
        		}
        		skip = 0;
        		do {
        			skip++;
        			nextType = wh.getRule().getRight().get(wh.getMatched()+skip).getType();
        			if (g.isNullable(nextType) && wh.getMatched()+skip+1==wh.getRule().getRight().size()) {
        				generateSymbol(g.getStartType(),wh);
        			}
        		} while (g.isNullable(nextType) && wh.getMatched()+skip+1<wh.getRule().getRight().size());
        	}
        }
                
        return pg;     
    }

    
    /**
     * Generate a handle and the corresponding waiting handles.
     * @param s the next symbol to consider
     * @param r the rule
     * @param matched the next element to match in the rule
     * @param first the first symbol of this match
     */
    private void addHandle (ParsedSymbol s, Rule r, int matched, InputSymbol first) 
    {
        Object nextType = r.getRight().get(matched).getType();
        Map<Object,Set<Handle>> thisCore = cores.get(s);
        Handle h;
        int skip = -1;

        do {
            skip++;
            nextType = r.getRight().get(matched+skip).getType();
            Set<Handle> tc = thisCore.get(nextType);
            h = new Handle(r,matched+skip,first.getStartIndex(),first);
            if (tc == null || !tc.contains(h)) {
                Set<Object> fs = g.getStar(nextType);
                if (fs != null) {
                    if (fs.contains(s.getType())) {
                        if (tc == null) {
                            tc = new HashSet<Handle>();
                            thisCore.put(nextType,tc);
                        }
                        if (matched+skip != 0)
                            tc.add(h);
                    }
                }
                
                if (nextType.equals(s.getType())) {
                    WaitingHandle w = new WaitingHandle(r,matched+skip,first.getStartIndex(),first,s);
                    Set<WaitingHandle> dh = doneHandles.get(s);
                    if (dh == null) {
                        dh = new HashSet<WaitingHandle>();
                        doneHandles.put(s, dh);
                    }
                    if (!dh.contains(w)) {
                        dh.add(w);
                        waitingHandlePool.add(w);
                    }
                }
            }
        } while (g.isNullable(nextType) && matched+skip+1<r.getRight().size());
    }

    /**
     * Generate a symbol
     */
    private void generateSymbol (Object startType, WaitingHandle wh) 
    {
        Set<Object> singleTypeHistory = new HashSet<Object>();
        int count = 0;
        
        for (RuleSymbol e: wh.getRule().getRight()) 
            if (!g.isNullable(e.getType())) 
                count++;
        if (count==1) {
            if (wh.getNext().getSingleTypeHistory() != null)
                singleTypeHistory.addAll(wh.getNext().getSingleTypeHistory());
            if (singleTypeHistory.contains(wh.getRule().getLeft().getType()))
                return; // Avoid cyclic rules!
            singleTypeHistory.add(wh.getRule().getLeft().getType());
        }
        
        ParsedSymbol s = new ParsedSymbol(wh.getRule().getLeft().getType(),wh.getFirst().getStartIndex(),wh.getNext().getEndIndex(),singleTypeHistory);

        if (!pg.contains(s)) {
            pg.addSymbol(s);
            cores.put(s,new HashMap<Object,Set<Handle>>());

            Set<ParsedSymbol> prec = pg.getPreceding(wh.getFirst());
            
            if (prec!=null)
            	for (ParsedSymbol p: prec)
            		pg.addLink(p,s);

            Set<ParsedSymbol> foll = pg.getFollowing(wh.getNext());

            if (foll != null)
            	for (ParsedSymbol p: foll)
            		pg.addLink(s,p);

            for (Set<Handle> handles: cores.get(wh.getFirst()).values())
                for (Handle h: handles) {
                    if (h.getMatched()==0)
                        addHandle(s,h.getRule(),h.getMatched(),s);
                    else
                        addHandle(s,h.getRule(),h.getMatched(),h.getFirst());
                }

            if (g.getStartRules(s.getType()) != null)
                for (Rule r: g.getStartRules(s.getType()))
                    addHandle(s,r,0,s);
            
            if (s.getType().equals(startType)) 
                if (s.getStartIndex()==lg.getInputStartIndex() && s.getEndIndex()==lg.getInputEndIndex())
                    pg.addStart(s);
        }
    }

}
